1. Field of the Invention
This invention relates generally to hard disk error correction code encoders and decoders, and more particularly to devices for generating check bytes and syndromes.
2. Description of the Related Art
Modem computer systems typically include one or more hard disk drives in which a large amount of data, including operating system files, application programs, and files may be stored. Hard disk drives typically store information in sequence by using magnetic technology. As is common in most recording technology, reading the sequential data bits from a hard disk often generates errors due to noise, manufacturing imperfections of the physical medium, dust, etc.
To detect and correct such errors, hard disk drives typically implement an error correction code (ECC) scheme in writing to and reading from hard disk drives. These hard disk drives generally include ECC circuitry that implements ECC schemes using well known codes such as Reed-Solomon code to encode user data to enable reliable recovery of the original data through the use of an ECC decoder. As is well known, ECC coding schemes assist in achieving a higher areal density.
In general, conventional ECC circuitry implements ECC encoders and syndrome generators in accordance with well known generator polynomials. For example, a Reed-Solomon encoder and syndrome generator may implement a generator polynomial g(X) as follows: EQU g(X)=(X+.alpha..sup.m)(X+.alpha..sup.m+1)(X+.alpha..sup.m+2)(X+.alpha..sup. m+3)(X+.alpha..sup.m+4)(X+.alpha..sup.m+5)=X.sup.6 +.alpha..sup.a X.sup.5 +.alpha..sup.b X.sup.4 +.alpha..sup.c X.sup.3 +.alpha..sup.d X.sup.2 +.alpha..sup.e X+.alpha..sup.f.
In the past, generator polynomials have been typically implemented through the use of linear feedback shift registers with feedback connections corresponding to coefficients of the generator polynomials. For example, in writing to a hard disk medium, traditional ECC encoders typically compute ECC check bytes for a given block of user data such as a sector by using linear feedback shift registers. Prior Art FIG. 1 illustrates a conventional ECC encoder 100 that is used in generating exemplary ECC check bytes employing a plurality of linear feedback shift registers 118, 120, 122, 124, 126, and 128. The shift registers 118, 120, 122, 124, 126, and 128 are initially set to zero.
The ECC encoder 100 includes a plurality of well known Galois Field (GF) adders 102, 130, 132, 134, 136, and 138, each of which is functionally equivalent to exclusive-OR (XOR) gates. The GF adder 102 sequentially receives a plurality of user data sectors (e.g., S1, S2, S3, etc.), each of which typically comprises 512 user data bytes. In particular, the GF adder 102 receives each of the user data sectors byte-wise, one byte at a time. The GF adder 102 performs an XOR operation on the inputs and feeds the output to constant multipliers 106, 108, 110, 112, 114, and 116, respectively, for multiplication with constants .alpha..sup.f, .alpha..sup.e, .alpha..sup.d, .alpha.a.sup.c, .alpha..sup.b, and .alpha..sup.a, respectively. An AND gate 104 is set to "1" to transmit the output from the GF adder 102 to the constant multipliers 106 through 116 as long as the GF adder 102 receives a user byte.
With continuing reference to Prior Art FIG. 1, the output of the constant multiplier 106 is fed into the shift register 118 while the outputs of the constant multipliers 108, 110, 112, 114, and 116, respectively, are fed into GF adders 130, 132, 134, 136, and 138, respectively. The GF adders 130, 132, 134, 136, 138, and 102 are also arranged to receive the contents of shift registers 118, 120, 122, 124, 126, and 128, respectively. The added output from each of the GF adders 130, 132, 134, 136, and 138 is then fed into shift registers 120, 122, 124, 126, and 128, respectively.
In this configuration, as the next byte of a sector is received, the contents of the shift registers 118, 120, 122, 124, 126, and 128, respectively, are used to generate a sum through the GF adders 130, 132, 134, 136, 138, and 102, respectively. After the last byte of a sector has been received and processed, the shift registers 118 through 128 will contain six check bytes. These six check bytes are then shifted out of the registers 118 through 128 as an output signal ECCCHK by feeding a "0" into an the AND gate 104. As the ECC check bytes are generated, the ECC bytes are appended to the sector of user data and then recorded (e.g., written) on a hard disk medium.
On the other hand, when recorded sectors of ECC encoded data are read from a hard disk medium, conventional ECC decoders decode the received data sectors including the ECC check bytes by generating partial syndromes for the ECC encoded data sectors. Partial syndromes are well known in the art and are used to detect errors in the associated sector (e.g. presence of errors, location of errors, and error patterns). Typically, conventional ECC decoders include a syndrome generator, which generates partial syndromes by using feedback shift registers.
Prior Art FIG. 2 illustrates a conventional ECC syndrome generator 200 that generates partial syndromes PS0, PS1, PS2, PS3, PS4, and PS5 by using a plurality of registers 202, 204, 206, 208, 210, and 212. The ECC syndrome generator 200 receives a stream of ECC encoded data sectors such as S1', S2', S3', etc. Each of the data sectors includes a plurality of ECC check bytes appended to the user data portion of the data sector.
The syndrome generator 200 includes a plurality of GF adders 214, 216, 218, 220, 222, and 224, which are configured to sequentially receive, as an input, the bytes of a data sector, one byte at a time. As in the ECC encoder 100, the GF adders 214 through 224 perform functions that are equivalent to XOR gates. A plurality of constant multipliers 226, 228, 230, 232, 234, and 236 are configured to receive and multiply the content of the feedback registers 202, 204, 206, 208, 210, and 212, respectively, with associated constants .alpha..sup.m, .alpha..sup.m+1, .alpha..sup.m+2, .alpha..sup.m-3, .alpha..sup.m+4, and .alpha..sup.m+5, respectively. The product from the constant multipliers 226, 228, 230, 232, 234, and 236 are then fed into the GF adders 214, 216, 218, 220, 222, and 224, respectively, an inputs. In this manner, the constant multipliers 226 through 236 provide a feedback path for the associated registers.
In this feedback register configuration, the registers 202 through 212 are initially set to zero before receiving the first byte of a data sector. Accordingly, the GF adders 214 through 224 merely pass the first byte to the associated shift register. Thereafter, the first byte from each of the registers 202 through 212 is multiplied with the associated constant. The resulting product is then provided to an associated GF adder as an input. The GF adders 214 through 224 then adds the associated input with the next data byte of the data sector. The sum of each of the GF adders 214 through 224 is then stored back into the associated register.
When the last byte (e.g., the last check byte) of the sector has been received and processed, the partial syndromes for the received sector is generated and stored in the registers 202, 204, 206, 208, 210, and 212. The generated partial syndromes indicate the presence of errors in the sector. From the partial syndromes, an ECC decoder may generate error locations and error patterns in the sector for error correction.
Unfortunately, the registers found in conventional ECC encoders and syndrome generators can become too costly when the number of check bytes are increased. For example, each additional check byte requires an additional register with supporting feedback circuit elements. Consequently, as the number of check bytes are increased to a high number, the use of registers may become too costly to implement.
Furthermore, conventional ECC circuitry typically includes a programmable interleaving degree feature to correct worst case error bursts of various lengths. Implementing the programmable interleaving degree, however, escalates the cost of the ECC circuitry. For example, an ECC encoder with interleaving degree of three generally requires three times the shift registers of an ECC encoder with no interleaving degree. In addition, accommodating a programmable interleaving degrees in these conventional ECC circuitry would require complex and costly multiplexing circuit within each shift stage. Hence, implementing linear feedback shift registers for providing programmable interleaving degrees may be economically impractical for ECC circuitry.
Thus, what is needed is a device and method that can implement ECC encoding and syndrome generation without the cost associated with linear feedback shift registers and supporting circuitry. What is further needed is a device and method that are readily scaleable to accommodate varying number of ECC check bytes, partial syndromes, and interleave degrees.